import functools
from typing import List


@functools.lru_cache(None)
def dfs_min(n_left, n_mid, n_right):
    # 记忆化递归情况数：9*9*10=810

    # 任何时候，只要左右相同，就一定会比赛
    if n_left == n_right:
        # print("MAX:", n_left, n_mid, n_right, "->", 1)
        return 1

    n = n_left + n_mid + n_right + 2
    remove = n // 2

    p1, p2 = 1 + n_left, n - n_right  # 两个选手的下标

    res = float("inf")
    for stat in range(1 << remove):  # 遍历每一种情况：2^14=16382
        n1, n2, n3 = n_left, n_mid, n_right
        for i in range(remove):
            pp1, pp2 = i + 1, n - i
            if stat & (1 << i):  # p1获胜
                if pp2 == p1 or pp2 == p2:
                    break  # 情况不存在
                if pp2 > p2:
                    n3 -= 1
                elif pp2 > p1:
                    n2 -= 1
                else:
                    n1 -= 1
            else:  # p2获胜
                if pp1 == p1 or pp1 == p2:
                    break  # 情况不存在
                if pp1 < p1:
                    n1 -= 1
                elif pp1 < p2:
                    n2 -= 1
                else:
                    n3 -= 1
        else:
            res = min(res, dfs_min(n1, n2, n3) + 1)

    return res


@functools.lru_cache(None)
def dfs_max(n_left, n_mid, n_right):
    # 记忆化递归情况数：9*9*10=810

    # 任何时候，只要左右相同，就一定会比赛
    if n_left == n_right:
        # print("MAX:", n_left, n_mid, n_right, "->", 1)
        return 1

    n = n_left + n_mid + n_right + 2
    remove = n // 2

    p1, p2 = 1 + n_left, n - n_right  # 两个选手的下标

    res = 0
    for stat in range(1 << remove):  # 遍历每一种情况：2^14=16382
        n1, n2, n3 = n_left, n_mid, n_right
        for i in range(remove):
            pp1, pp2 = i + 1, n - i
            if stat & (1 << i):  # p1获胜
                if pp2 == p1 or pp2 == p2:
                    break  # 情况不存在
                if pp2 > p2:
                    n3 -= 1
                elif pp2 > p1:
                    n2 -= 1
                else:
                    n1 -= 1
            else:  # p2获胜
                if pp1 == p1 or pp1 == p2:
                    break  # 情况不存在
                if pp1 < p1:
                    n1 -= 1
                elif pp1 < p2:
                    n2 -= 1
                else:
                    n3 -= 1
        else:
            res = max(res, dfs_max(n1, n2, n3) + 1)

    return res


class Solution:
    def earliestAndLatest(self, n: int, first: int, second: int) -> List[int]:
        if first > second:
            first, second = second, first

        n_left = first - 1  # 左侧人数
        n_mid = second - first - 1  # 中间人数
        n_right = n - second  # 右侧人数

        return [dfs_min(n_left, n_mid, n_right), dfs_max(n_left, n_mid, n_right)]


if __name__ == "__main__":
    print(Solution().earliestAndLatest(n=11, first=2, second=4))  # [3,4]
    print(Solution().earliestAndLatest(n=5, first=1, second=5))  # [1,1]

    # 测试用例129/136
    print(Solution().earliestAndLatest(n=5, first=1, second=4))  # [2,2]
